#include "Alloc.hh"

namespace snow
{

char *Alloc::_start_free = 0;
char *Alloc::_end_free = 0;
size_t Alloc::_heap_size = 0;

Alloc::_obj *Alloc::_free_list[Alloc::_NFREELISTS] = {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

void *Alloc::allocate(size_t bytes)
{
    // 申请大于128字节的空间，直接malloc
    if (bytes > (size_t)_MAXBYTES) {
        return malloc(bytes);
    }
    _obj **my_free_list = _free_list + FREELIST_INDEX(bytes);
    _obj *result = *my_free_list;
    if (0 == result) { // 如果空闲链表上没有，就调用refill填充链表
        void *ret = refill(ROUND_UP(bytes));
        return ret;
    }
    // 如果有，就从链表上取一块空间
    *my_free_list = result->next;
    return result;
}

void Alloc::deallocate(void *p, size_t bytes)
{
    if (bytes > _MAXBYTES) {
        free(p);
        return;
    } 
    // 小于128，挂到相应的index下，头插法
    size_t index = FREELIST_INDEX(bytes);
    _obj *node = (_obj *)(p);
    node->next = _free_list[index];
    _free_list[index] = node;
}

void *Alloc::reallocate(void *p, size_t old_sz, size_t new_sz)
{
    deallocate(p, old_sz);
    return allocate(new_sz);
}

/**
 * @brief {Life is too short to learn cpp.}
 * 
 * @param bytes 一个区块的大小，已经是8的倍数
 * @return void* 返回一个区块的指针（剩余挂到freelist上）
 * 
 * 无需顾虑，refill的情况肯定是当前链表上已经无区块了！
 * 重新填充freelist，新的空间取自内存池（由chunk_alloc完成）
 * 默认取20个区块，若内存池不够则可能小于20，具体策略见chunk_alloc
 */
void *Alloc::refill(size_t bytes)
{
    size_t nobjs = _NOBJS; // 20
    // chunk_alloc内部会递归调用，修正nobjs
    // chunk即从内存池获取的内存
    char *chunk = chunk_alloc(bytes, nobjs);
    if (1 == nobjs) { // 若只有一个区块，就给用户返回，链表无更新
        return chunk;
    }
    // 不只一个区块，一个给用户，剩下的挂到链表上
    // 当前index下肯定是没空闲区块挂着了，否则也不会调用refill~
    _obj **my_free_list = _free_list + FREELIST_INDEX(bytes);
    _obj *result = (_obj *)chunk; // 第一块给用户返回
    _obj *current_obj = 0, *next_obj = 0;
    *my_free_list = next_obj = (_obj *)(chunk + bytes); // 头插法
    for (int i = 1;; ++i) {
        current_obj = next_obj;
        next_obj = (_obj *)((char *)next_obj + bytes);
        if (nobjs - 1 == i) {
            current_obj->next = 0;
            break;
        } else {
            current_obj->next = next_obj;
        }
    }
    return result;
}

/**
 * @brief {Life is too short to learn cpp.}
 * 
 * @param bytes 分配字节数，已是8的整数倍，即一个区块的大小
 * @param nobjs 区块个数
 * @return char* 
 * 
 * 分配策略：
 * 优先从内存池取20个区块，若不够20块则有多少块拿多少块。
 * 若连一块也没有，才会从堆中malloc，为 内存池注“水”
 * 若malloc失败则从freelist上寻 for (i = bytes; i <= 128; i += 8)，
 * 如果找到先放进内存池，后面再递归调用自己，修正nobjs
 */
char *Alloc::chunk_alloc(size_t bytes, size_t &nobjs)
{
    char *result = 0;
    size_t total_bytes = bytes * nobjs;
    size_t bytes_left = _end_free - _start_free; // 内存池剩余空间

    if (bytes_left >= total_bytes) {
        // 内存池满足需求
        result = _start_free;
        _start_free += total_bytes;
        return result;
    } else if (bytes_left >= bytes) {
        // 内存池剩余空间>=一个块儿
        nobjs = bytes_left / bytes;
        total_bytes = bytes * nobjs; // 剩几个块儿拿走几个
        result = _start_free;
        _start_free += total_bytes;
        return result;
    } else {
        // 内存池无法提供一个区块，就从堆空间申请吧
        // 一次申请40个块儿
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(_heap_size >> 4);
        if (bytes_left > 0) {
            // 如果内存池还有点，就把它挂到相应的空闲链表上
            _obj **my_free_list = _free_list + FREELIST_INDEX(bytes_left);
            ((_obj *)_start_free)->next = *my_free_list; // 头插法
            *my_free_list = (_obj *)_start_free;
        }
        _start_free = (char *)malloc(bytes_to_get);
        if (0 == _start_free) {
            // malloc返回零！堆空间耗尽
            // 不打算从堆空间申请更小的空间，因为在多进程中容易出问题
            // 去空闲链表上找，怎么找？从当前bytes起始遍历
            _obj **my_free_list = 0;
            _obj *p = 0;
            for (int i = bytes; i <= _MAXBYTES; i += _ALIGN) {
                my_free_list = _free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if (p != 0) { // 空闲链表上有东西，先放入内存池中
                    *my_free_list = p->next;
                    _start_free = (char *)p;
                    _end_free = _start_free + i;
                    // 递归调用chunk_alloc 修正nobjs
                    return chunk_alloc(bytes, nobjs);
                }
            }
            _end_free = 0; // 山穷水尽，到处都没了
            // 调用一级配置器，这边没写...
        }
        _heap_size += bytes_to_get;
        _end_free = _start_free + bytes_to_get;
        // 递归调用chunk_alloc 修正nobjs
        return chunk_alloc(bytes, nobjs);
    }
}

} //namespace snow